#include <stdio.h>
#define Arraylen(a) sizeof(a) / sizeof(a[0])

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int IsBigger(int a, int b)
{
    if (a > b)
        return 1;
    else
        return 0;
}
int IsSmaller(int a, int b)
{
    if (a < b)
        return 1;
    else
        return 0;
}
void BubbleSort(int *a, int len, int (*Rule)(int, int))
{
    // compare times
    for (int i = 0; i < len - 1; i++)
    {
        int flag = 0;
        for (int j = 0; j < len - i - 1; j++)
        {
            if (Rule(a[j], a[j + 1]))
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = 1;
            }
        }
        if (flag == 0)
            break;
    }
}
void InsertSort(int *a, int len)
{
    for (int i = 0; i < len; i++)
    {
        int temp = a[i];
        int j = i;
        for (; j > 0; j--)
        {
            if (a[j - 1] > temp)
            {
                a[j] = a[j - 1];
            }
            else
            {
                break;
            }
        }
        a[j] = temp;
    }
}
void ChooseSort(int *a, int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < len; j++)
        {
            if (a[j] < a[min])
            {
                min = j;
            }
        }
        swap(a + i, a + min);
    }
}

void ChooseSort2(int *a, int len)
{
    int left = 0;
    int right = len - 1;
    while (left < right)
    {
        int min = left;
        int max = right;
        for (int i = left; i <= right; i++)
        {
            if (a[i] < a[min])
                min = i;
            if (a[i] > a[max])
                max = i;
        }
        swap(&a[left], &a[min]);
        if (max == left)
        {
            max = min;
        }
        swap(&a[right], &a[max]);

        left++;
        right--;
    }
}
void FastSort(int *a, int start, int end)
{
    int left = start;
    int right = end;
    int temp = a[start];
    while (left < right)
    {
        while (left < right && a[right] > temp)
        {
            right--;
        }
        if (left < right)
        {
            a[left] = a[right];
            left++;
        }
        while (left < right && a[left] < temp)
        {
            left++;
        }
        if (left < right)
        {
            a[right] = a[left];
            right--;
        }
        a[left] = temp;
        FastSort(a, start, left - 1);
        FastSort(a, right + 1, end);
    }
}
int main()
{
    int a[] = {3, 6, 8, 2, 1, 9};
    FastSort(a, 0, Arraylen(a));
    for (int i = 0; i < Arraylen(a); i++)
    {
        printf("%d ", a[i]);
    }                         
    return 0;
}